// 二分查找 - 利用数组的 二段性 解决问题，每次可以舍弃一段数据
// 经典在 有序数组中 找一个数/找一个数的插入位置 的问题，都可以使用二分查找
// 要求时间复杂度为 O(log n) 的题目，通常使用二分查找

// 例题 3：
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
// 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//
//        请必须使用时间复杂度为 O(log n) 的算法。
//
//        示例 1:
//
//        输入: nums = [1,3,5,6], target = 5
//        输出: 2
//        示例 2:
//
//        输入: nums = [1,3,5,6], target = 2
//        输出: 1
//        示例 3:
//
//        输入: nums = [1,3,5,6], target = 7
//        输出: 4
//
//
//        提示:
//
//        1 <= nums.length <= 104
//        -104 <= nums[i] <= 104
//        nums 为 无重复元素 的 升序 排列数组
//        -104 <= target <= 104

// 解题思路：
// 找左端点，左端点的位置就是需要插入的位置
// 左中点：mid = left + (right - left) / 2
// x < target: left = mid + 1;
// x >= target: right = mid

public class SearchInsert {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        if(nums[right] < target) return n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}
